package com.hy.study.practice.linkedlist;

/**
 * 链表实现约瑟夫环问题
 */
public class JosephCircleDemo {
    public static void main(String[] args) {
        JosephLinkedList josephLinkedList = new JosephLinkedList();
        josephLinkedList.init(5);
        josephLinkedList.list();
        josephLinkedList.countOrderBy(1,2,5);
    }
}

/**
 * 约瑟夫环
 */
class JosephLinkedList {

    private PersonNode first = null;

    public boolean isEmpty() {
        return first == null;
    }


    /**
     * 初始化约瑟夫环
     *
     * @param size 多少个人
     */
    public void init(int size) {
        PersonNode temp = null;
        for (int i = 1; i <= size; i++) {
            if (i == 1) {
                first = new PersonNode(i, i + "同学");
                first.setNextNode(first);
                temp = first.getNextNode();
            } else {
                PersonNode personNode = new PersonNode(i, i + "同学");
                temp.setNextNode(personNode);
                personNode.setNextNode(first);
                temp = personNode;
            }
        }
    }

    /**
     * 展示约瑟夫环
     */
    public void list() {
        if (isEmpty()) {
            System.out.println("环为空");
            return;
        }
        PersonNode node = first;
        while (true) {
            System.out.println(node);
            node = node.getNextNode();
            if(node == first){
                break;
            }
        }
    }

    /**
     * 出队
     *
     * @param i 从第几个人开始
     * @param k 每次报数多少个
     * @param n 总共多少个人
     */
    public void countOrderBy(int i, int k, int n) {
        if (i < 0 || i > n || k < 1 || k > n) {
            System.out.println("参数有误");
            return;
        }
        PersonNode helper = first;
        while (helper.getNextNode()!=first){
            helper=helper.getNextNode();
        }
        for (int j = 1; j < i ; j++) {
            helper = helper.getNextNode();
            first = first.getNextNode();
        }
        while (true) {
            if ( first==helper) {
                break;
            }else{
                for (int j = 1; j <k ; j++) {
                    helper = helper.getNextNode();
                    first = first.getNextNode();
                }
                System.out.println("出队:" + first);
                first = first.getNextNode();
                helper.setNextNode(first);
            }
        }
        System.out.println("最后出队的:" + first);
    }
}

class PersonNode {
    private int no;
    private String name;
    private PersonNode nextNode;

    public PersonNode() {
    }

    public PersonNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public PersonNode getNextNode() {
        return nextNode;
    }

    public void setNextNode(PersonNode nextNode) {
        this.nextNode = nextNode;
    }

    @Override
    public String toString() {
        return "PersonNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}